Set Systems and Families of Permutations with Small Traces
Identifieur interne : 003C39 ( Main/Exploration ); précédent : 003C38; suivant : 003C40Set Systems and Families of Permutations with Small Traces
Auteurs : Otfried Cheong [Corée du Sud] ; Xavier Goaoc [France] ; Cyril Nicaud [France]Source :
Descripteurs français
Abstract
We study the maximum size of a set system on $n$ elements whose trace on any $b$ elements has size at most $k$. We show that if for some $b \ge i \ge 0$ the shatter function $f_R$ of a set system $([n],R)$ satisfies $f_R(b) < 2^i(b-i+1)$ then $|R| = O(n^i)$; this generalizes Sauer's Lemma on the size of set systems with bounded VC-dimension. We use this bound to delineate the main growth rates for the same problem on families of permutations, where the trace corresponds to the inclusion for permutations. This is related to a question of Raz on families of permutations with bounded VC-dimension that generalizes the Stanley-Wilf conjecture on permutations with excluded patterns.
Url:
Affiliations:
- Corée du Sud, France
- Grand Est, Lorraine (région)
- Nancy
- Institut national polytechnique de Lorraine, Université Nancy 2, Université de Lorraine
Links toward previous steps (curation, corpus...)
- to stream Hal, to step Corpus: 004540
- to stream Hal, to step Curation: 004540
- to stream Hal, to step Checkpoint: 002E85
- to stream Main, to step Merge: 003D52
- to stream Main, to step Curation: 003C39
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Set Systems and Families of Permutations with Small Traces</title><author><name sortKey="Cheong, Otfried" sort="Cheong, Otfried" uniqKey="Cheong O" first="Otfried" last="Cheong">Otfried Cheong</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-121665" status="VALID"><orgName>Department of Electrical Engineering [Korea Advanced Institute of Science and Technology]</orgName><orgName type="acronym">KAIST</orgName><desc><address><addrLine>335 Gwahak-ro (373-1 Guseong-dong) Yuseong-gu, Daejeon 305-701 Republic of Korea</addrLine><country key="KR"></country></address><ref type="url">http://www.kaist.edu/edu.html</ref></desc><listRelation><relation active="#struct-365285" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-365285" type="direct"><org type="institution" xml:id="struct-365285" status="INCOMING"><orgName>Korea Advanced Institute of Science and Technology</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>Corée du Sud</country></affiliation></author><author><name sortKey="Goaoc, Xavier" sort="Goaoc, Xavier" uniqKey="Goaoc X" first="Xavier" last="Goaoc">Xavier Goaoc</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-2573" status="OLD"><idno type="RNSR">200518305E</idno><orgName>Effective Geometric Algorithms for Surfaces and Visibility</orgName><orgName type="acronym">VEGAS</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.inria.fr/equipes/vegas</ref></desc><listRelation><relation active="#struct-160" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-300291" type="indirect"></relation><relation active="#struct-300292" type="indirect"></relation><relation active="#struct-300293" type="indirect"></relation><relation active="#struct-2496" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-160" type="direct"><org type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation name="UMR7503" active="#struct-441569" type="direct"></relation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-300291" type="direct"></relation><relation active="#struct-300292" type="direct"></relation><relation active="#struct-300293" type="direct"></relation></listRelation></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-300291" type="indirect"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName><orgName type="acronym">UHP</orgName><date type="end">2011-12-31</date><desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300292" type="indirect"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName><date type="end">2011-12-31</date><desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300293" type="indirect"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName><orgName type="acronym">INPL</orgName><date type="end">2011-12-31</date><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-2496" type="direct"><org type="laboratory" xml:id="struct-2496" status="OLD"><orgName>INRIA Lorraine</orgName><desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/centre-de-recherche-inria/nancy-grand-est</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université Nancy 2</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Institut national polytechnique de Lorraine</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName></affiliation></author><author><name sortKey="Nicaud, Cyril" sort="Nicaud, Cyril" uniqKey="Nicaud C" first="Cyril" last="Nicaud">Cyril Nicaud</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-3210" status="VALID"><idno type="RNSR">200212717U</idno><orgName>Laboratoire d'Informatique Gaspard-Monge</orgName><orgName type="acronym">LIGM</orgName><desc><address><addrLine>Université de Paris-Est - Marne-la-Vallée, Cité Descartes, Bâtiment Copernic, 5 bd Descartes, 77454 Marne-la-Vallée Cedex 2, Inst Gaspard Monge</addrLine><country key="FR"></country></address><ref type="url">http://ligm.u-pem.fr</ref></desc><listRelation><relation active="#struct-301243" type="direct"></relation><relation active="#struct-301545" type="direct"></relation><relation active="#struct-302085" type="direct"></relation><relation active="#struct-304949" type="direct"></relation><relation name="UMR8049" active="#struct-441569" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-301243" type="direct"><org type="institution" xml:id="struct-301243" status="VALID"><orgName>Université Paris-Est Marne-la-Vallée</orgName><orgName type="acronym">UPEM</orgName><desc><address><addrLine>5 boulevard Descartes - Champs-sur-Marne - 77454 Marne-la-Vallée Cedex2 </addrLine><country key="FR"></country></address><ref type="url">http://www.u-pem.fr/</ref></desc></org></tutelle><tutelle active="#struct-301545" type="direct"><org type="institution" xml:id="struct-301545" status="OLD"><orgName>École des Ponts ParisTech (ENPC)</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-302085" type="direct"><org type="institution" xml:id="struct-302085" status="VALID"><orgName>Fédération de Recherche Bézout</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-304949" type="direct"><org type="institution" xml:id="struct-304949" status="INCOMING"><orgName>ESIEE</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle name="UMR8049" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">HAL</idno><idno type="RBID">Hal:inria-00441376</idno><idno type="halId">inria-00441376</idno><idno type="halUri">https://hal.inria.fr/inria-00441376</idno><idno type="url">https://hal.inria.fr/inria-00441376</idno><date when="2009">2009</date><idno type="wicri:Area/Hal/Corpus">004540</idno><idno type="wicri:Area/Hal/Curation">004540</idno><idno type="wicri:Area/Hal/Checkpoint">002E85</idno><idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">002E85</idno><idno type="wicri:Area/Main/Merge">003D52</idno><idno type="wicri:Area/Main/Curation">003C39</idno><idno type="wicri:Area/Main/Exploration">003C39</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Set Systems and Families of Permutations with Small Traces</title><author><name sortKey="Cheong, Otfried" sort="Cheong, Otfried" uniqKey="Cheong O" first="Otfried" last="Cheong">Otfried Cheong</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-121665" status="VALID"><orgName>Department of Electrical Engineering [Korea Advanced Institute of Science and Technology]</orgName><orgName type="acronym">KAIST</orgName><desc><address><addrLine>335 Gwahak-ro (373-1 Guseong-dong) Yuseong-gu, Daejeon 305-701 Republic of Korea</addrLine><country key="KR"></country></address><ref type="url">http://www.kaist.edu/edu.html</ref></desc><listRelation><relation active="#struct-365285" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-365285" type="direct"><org type="institution" xml:id="struct-365285" status="INCOMING"><orgName>Korea Advanced Institute of Science and Technology</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>Corée du Sud</country></affiliation></author><author><name sortKey="Goaoc, Xavier" sort="Goaoc, Xavier" uniqKey="Goaoc X" first="Xavier" last="Goaoc">Xavier Goaoc</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-2573" status="OLD"><idno type="RNSR">200518305E</idno><orgName>Effective Geometric Algorithms for Surfaces and Visibility</orgName><orgName type="acronym">VEGAS</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.inria.fr/equipes/vegas</ref></desc><listRelation><relation active="#struct-160" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-300291" type="indirect"></relation><relation active="#struct-300292" type="indirect"></relation><relation active="#struct-300293" type="indirect"></relation><relation active="#struct-2496" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-160" type="direct"><org type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation name="UMR7503" active="#struct-441569" type="direct"></relation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-300291" type="direct"></relation><relation active="#struct-300292" type="direct"></relation><relation active="#struct-300293" type="direct"></relation></listRelation></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-300291" type="indirect"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName><orgName type="acronym">UHP</orgName><date type="end">2011-12-31</date><desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300292" type="indirect"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName><date type="end">2011-12-31</date><desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300293" type="indirect"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName><orgName type="acronym">INPL</orgName><date type="end">2011-12-31</date><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-2496" type="direct"><org type="laboratory" xml:id="struct-2496" status="OLD"><orgName>INRIA Lorraine</orgName><desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/centre-de-recherche-inria/nancy-grand-est</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université Nancy 2</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Institut national polytechnique de Lorraine</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName></affiliation></author><author><name sortKey="Nicaud, Cyril" sort="Nicaud, Cyril" uniqKey="Nicaud C" first="Cyril" last="Nicaud">Cyril Nicaud</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-3210" status="VALID"><idno type="RNSR">200212717U</idno><orgName>Laboratoire d'Informatique Gaspard-Monge</orgName><orgName type="acronym">LIGM</orgName><desc><address><addrLine>Université de Paris-Est - Marne-la-Vallée, Cité Descartes, Bâtiment Copernic, 5 bd Descartes, 77454 Marne-la-Vallée Cedex 2, Inst Gaspard Monge</addrLine><country key="FR"></country></address><ref type="url">http://ligm.u-pem.fr</ref></desc><listRelation><relation active="#struct-301243" type="direct"></relation><relation active="#struct-301545" type="direct"></relation><relation active="#struct-302085" type="direct"></relation><relation active="#struct-304949" type="direct"></relation><relation name="UMR8049" active="#struct-441569" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-301243" type="direct"><org type="institution" xml:id="struct-301243" status="VALID"><orgName>Université Paris-Est Marne-la-Vallée</orgName><orgName type="acronym">UPEM</orgName><desc><address><addrLine>5 boulevard Descartes - Champs-sur-Marne - 77454 Marne-la-Vallée Cedex2 </addrLine><country key="FR"></country></address><ref type="url">http://www.u-pem.fr/</ref></desc></org></tutelle><tutelle active="#struct-301545" type="direct"><org type="institution" xml:id="struct-301545" status="OLD"><orgName>École des Ponts ParisTech (ENPC)</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-302085" type="direct"><org type="institution" xml:id="struct-302085" status="VALID"><orgName>Fédération de Recherche Bézout</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-304949" type="direct"><org type="institution" xml:id="struct-304949" status="INCOMING"><orgName>ESIEE</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle name="UMR8049" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country></affiliation></author></analytic></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="mix" xml:lang="fr"><term>Permutation pattern</term><term>Sauer Lemma</term><term>Set systems</term><term>VC dimension</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">We study the maximum size of a set system on $n$ elements whose trace on any $b$ elements has size at most $k$. We show that if for some $b \ge i \ge 0$ the shatter function $f_R$ of a set system $([n],R)$ satisfies $f_R(b) < 2^i(b-i+1)$ then $|R| = O(n^i)$; this generalizes Sauer's Lemma on the size of set systems with bounded VC-dimension. We use this bound to delineate the main growth rates for the same problem on families of permutations, where the trace corresponds to the inclusion for permutations. This is related to a question of Raz on families of permutations with bounded VC-dimension that generalizes the Stanley-Wilf conjecture on permutations with excluded patterns.</div></front></TEI><affiliations><list><country><li>Corée du Sud</li><li>France</li></country><region><li>Grand Est</li><li>Lorraine (région)</li></region><settlement><li>Nancy</li></settlement><orgName><li>Institut national polytechnique de Lorraine</li><li>Université Nancy 2</li><li>Université de Lorraine</li></orgName></list><tree><country name="Corée du Sud"><noRegion><name sortKey="Cheong, Otfried" sort="Cheong, Otfried" uniqKey="Cheong O" first="Otfried" last="Cheong">Otfried Cheong</name></noRegion></country><country name="France"><region name="Grand Est"><name sortKey="Goaoc, Xavier" sort="Goaoc, Xavier" uniqKey="Goaoc X" first="Xavier" last="Goaoc">Xavier Goaoc</name></region><name sortKey="Nicaud, Cyril" sort="Nicaud, Cyril" uniqKey="Nicaud C" first="Cyril" last="Nicaud">Cyril Nicaud</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 003C39 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 003C39 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= Hal:inria-00441376
|texte= Set Systems and Families of Permutations with Small Traces
}}
| This area was generated with Dilib version V0.6.33. |  |